package subjectlist;

import javax.sound.midi.Soundbank;
import java.util.concurrent.Callable;

/**
 * 给定数组a1, a2, a3, …, an，要求找出数组中的最大值和最小值。假设数组中的值两两各不相同。
 */
public class B如何查找数组中元素的最大值和最小值 {


    private static class A分治法{

        /**
         * 分治法就是将一个规模为n的、难以直接解决的大问题，分割为k个规模较小的子问题，
         * 采取各个击破、分而治之的策略得到各个子问题的解，
         * 然后将各个子问题的解进行合并，从而得到原问题的解的一种方法
         *
         * 本题中，当采用分治法求解时，就是将数组两两一对分组，如果数组元素个数为奇数个，
         * 就把最后一个元素单独分为一组，然后分别对每一组中相邻的两个元素进行比较，
         * 把二者中值小的数放在数组的左边，值大的数放在数组右边，
         * 只需要比较n/2 次就可以将数组分组完成。然后可以得出结论：最小值一定在每一组的左边部分，
         * 最大值一定在每一组的右边部分，接着只需要在每一组的左边部分找最小值，右边部分找最大值，
         * 查找分别需要比较n/2-1次和n/2-1次。因此，总共比较的次数大约为n/2*3=3n/2-2次
         */

        private int max;
        private int min;
        public int getMax(){
            return max;
        }
        public int getMin(){
            return min;
        }

        public void getMaxAndMin(int arr[]){
            if (arr == null) {
                System.out.println("参数不合法");
                return;
            }
            int i=0;
            int len=arr.length;
            max=arr[0];
            min=arr[0];
            //两两分组，把较小的数放到左半部分，较大的放到右半部分
            for (i = 0; i <len-1 ; i+=2) {
                if(arr[i]>arr[i+1]){
                    int tmp=arr[i];
                    arr[i]=arr[i+1];
                    arr[i+1]=tmp;
                }
            }
            min=arr[0];
            for (i = 2; i <len ; i+=2) {
                if(arr[i]<min){
                    min=arr[i];
                }
            }
            //在各个分组的右半部分找最小值
            max=arr[1];
            for (i = 3; i <len ; i+=2) {
                if (arr[i] > max) {
                    max=arr[i];
                }
            }
            //如果数组中元素个数是奇数个，最后一个元素被分为一组，需要特殊处理
            if (len % 2 == 1) {
                if(max<arr[len-1]){
                    max=arr[len-1];
                }
                if(min>arr[len-1]){
                    min=arr[len-1];
                }
            }
        }

        public static void main(String[] args) {
            int[]array={7,3,19,40,4,7,1};
            A分治法 m=new A分治法();
            m.getMaxAndMin(array);
            System.out.println("max="+m.getMax());
            System.out.println("min="+m.getMin());
        }
    }

    private static class B变形分治法{

        /**
         * 除了以上所示的分治法以外，还有一种分治法的变形，
         *
         * 其具体步骤如下：
         * 将数组分成左右两部分，先求出左半部分的最大值和最小值，
         * 再求出右半部分的最大值和最小值，然后综合起来，
         * 左右两部分的最大值中的较大值即为合并后的数组的最大值，
         * 左右两部分的最小值中的较小值即为合并后的数组的最小值，
         * 通过此种方法即可求合并后的数组的最大值与最小值。
         *
         * 以上过程是个递归过程，对于划分后的左右两部分，同样重复这个过程，
         * 直到划分区间内只剩一个元素或者两个元素为止
         */

    }
}
